package top.starp.bili;

import java.util.*;


/**
 * 过了4/5
 * https://www.nowcoder.com/question/next?pid=30021598&qid=1555613&tid=59361729
 */
public class Solution {
    /**
     *
     * @param grid int整型二维数组
     * @return int整型
     */
    public int minPathSum (int[][] grid) {
        // write code here
        //int maxN=99999;
        //int maxN=69999;
         int maxN=19999;

          int rowMax=grid.length-1;
        int colMax=grid[0].length-1;

        int [][]dp=new int[rowMax+1][colMax+1];
      // row
         dp[0][0]=grid[0][0];
        for(int i=1;i<grid.length;i++){
            dp[i][0]=grid[i][0]+dp[i-1][0];
        }


        for(int i=1;i<grid.length;i++){
            dp[0][i]=grid[0][i]+dp[0][i-1];
        }
        for(int i=1;i<grid.length;i++){
            for(int j=1;j<grid[0].length;j++){
              dp[i][j]=  Math.min(dp[i-1][j]+grid[i][j],
                       dp[i][j-1]+grid[i][j] );
               // dp[i][j]=dp[i-1][j]+grid[i][j];
            }
        }

        return dp[rowMax][colMax];
    }
}
